// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/metrics/sample_vector.h"

#include "base/logging.h"
#include "base/metrics/bucket_ranges.h"

namespace base {

typedef HistogramBase::Count Count;
typedef HistogramBase::Sample Sample;

SampleVector::SampleVector(const BucketRanges* bucket_ranges)
    : SampleVector(0, bucket_ranges)
{
}

SampleVector::SampleVector(uint64_t id, const BucketRanges* bucket_ranges)
    : HistogramSamples(id)
    , local_counts_(bucket_ranges->bucket_count())
    , counts_(&local_counts_[0])
    , counts_size_(local_counts_.size())
    , bucket_ranges_(bucket_ranges)
{
    CHECK_GE(bucket_ranges_->bucket_count(), 1u);
}

SampleVector::SampleVector(uint64_t id,
    HistogramBase::AtomicCount* counts,
    size_t counts_size,
    Metadata* meta,
    const BucketRanges* bucket_ranges)
    : HistogramSamples(id, meta)
    , counts_(counts)
    , counts_size_(bucket_ranges->bucket_count())
    , bucket_ranges_(bucket_ranges)
{
    CHECK_LE(bucket_ranges_->bucket_count(), counts_size_);
    CHECK_GE(bucket_ranges_->bucket_count(), 1u);
}

SampleVector::~SampleVector() { }

void SampleVector::Accumulate(Sample value, Count count)
{
    size_t bucket_index = GetBucketIndex(value);
    subtle::NoBarrier_AtomicIncrement(&counts_[bucket_index], count);
    IncreaseSum(static_cast<int64_t>(count) * value);
    IncreaseRedundantCount(count);
}

Count SampleVector::GetCount(Sample value) const
{
    size_t bucket_index = GetBucketIndex(value);
    return subtle::NoBarrier_Load(&counts_[bucket_index]);
}

Count SampleVector::TotalCount() const
{
    Count count = 0;
    for (size_t i = 0; i < counts_size_; i++) {
        count += subtle::NoBarrier_Load(&counts_[i]);
    }
    return count;
}

Count SampleVector::GetCountAtIndex(size_t bucket_index) const
{
    DCHECK(bucket_index < counts_size_);
    return subtle::NoBarrier_Load(&counts_[bucket_index]);
}

std::unique_ptr<SampleCountIterator> SampleVector::Iterator() const
{
    return std::unique_ptr<SampleCountIterator>(
        new SampleVectorIterator(counts_, counts_size_, bucket_ranges_));
}

bool SampleVector::AddSubtractImpl(SampleCountIterator* iter,
    HistogramSamples::Operator op)
{
    HistogramBase::Sample min;
    HistogramBase::Sample max;
    HistogramBase::Count count;

    // Go through the iterator and add the counts into correct bucket.
    size_t index = 0;
    while (index < counts_size_ && !iter->Done()) {
        iter->Get(&min, &max, &count);
        if (min == bucket_ranges_->range(index) && max == bucket_ranges_->range(index + 1)) {
            // Sample matches this bucket!
            subtle::NoBarrier_AtomicIncrement(
                &counts_[index], op == HistogramSamples::ADD ? count : -count);
            iter->Next();
        } else if (min > bucket_ranges_->range(index)) {
            // Sample is larger than current bucket range. Try next.
            index++;
        } else {
            // Sample is smaller than current bucket range. We scan buckets from
            // smallest to largest, so the sample value must be invalid.
            return false;
        }
    }

    return iter->Done();
}

// Use simple binary search.  This is very general, but there are better
// approaches if we knew that the buckets were linearly distributed.
size_t SampleVector::GetBucketIndex(Sample value) const
{
    size_t bucket_count = bucket_ranges_->bucket_count();
    CHECK_GE(bucket_count, 1u);
    CHECK_GE(value, bucket_ranges_->range(0));
    CHECK_LT(value, bucket_ranges_->range(bucket_count));

    size_t under = 0;
    size_t over = bucket_count;
    size_t mid;
    do {
        DCHECK_GE(over, under);
        mid = under + (over - under) / 2;
        if (mid == under)
            break;
        if (bucket_ranges_->range(mid) <= value)
            under = mid;
        else
            over = mid;
    } while (true);

    DCHECK_LE(bucket_ranges_->range(mid), value);
    CHECK_GT(bucket_ranges_->range(mid + 1), value);
    return mid;
}

SampleVectorIterator::SampleVectorIterator(
    const std::vector<HistogramBase::AtomicCount>* counts,
    const BucketRanges* bucket_ranges)
    : counts_(&(*counts)[0])
    , counts_size_(counts->size())
    , bucket_ranges_(bucket_ranges)
    , index_(0)
{
    CHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
    SkipEmptyBuckets();
}

SampleVectorIterator::SampleVectorIterator(
    const HistogramBase::AtomicCount* counts,
    size_t counts_size,
    const BucketRanges* bucket_ranges)
    : counts_(counts)
    , counts_size_(counts_size)
    , bucket_ranges_(bucket_ranges)
    , index_(0)
{
    CHECK_GE(bucket_ranges_->bucket_count(), counts_size_);
    SkipEmptyBuckets();
}

SampleVectorIterator::~SampleVectorIterator() { }

bool SampleVectorIterator::Done() const
{
    return index_ >= counts_size_;
}

void SampleVectorIterator::Next()
{
    DCHECK(!Done());
    index_++;
    SkipEmptyBuckets();
}

void SampleVectorIterator::Get(HistogramBase::Sample* min,
    HistogramBase::Sample* max,
    HistogramBase::Count* count) const
{
    DCHECK(!Done());
    if (min != NULL)
        *min = bucket_ranges_->range(index_);
    if (max != NULL)
        *max = bucket_ranges_->range(index_ + 1);
    if (count != NULL)
        *count = subtle::NoBarrier_Load(&counts_[index_]);
}

bool SampleVectorIterator::GetBucketIndex(size_t* index) const
{
    DCHECK(!Done());
    if (index != NULL)
        *index = index_;
    return true;
}

void SampleVectorIterator::SkipEmptyBuckets()
{
    if (Done())
        return;

    while (index_ < counts_size_) {
        if (subtle::NoBarrier_Load(&counts_[index_]) != 0)
            return;
        index_++;
    }
}

} // namespace base
